public class BinarySearchTree {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public TreeNode root;
    //插入
    public boolean insert(int key){
        if(root==null){
            root = new TreeNode(key);
            return true;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur!=null){
            if(cur.val>key){
                prev = cur;
                cur = cur.left;
            }else if(cur.val<key){
                prev = cur;
                cur = cur.right;
            }else{
                return false;
            }
        }
        TreeNode newnode = new TreeNode(key);
        if(newnode.val>prev.val){
            prev.right = newnode;
        }else{
            prev.left = newnode;
        }
        return true;
    }
    //查找
    public TreeNode search(int key){
        TreeNode cur = root;
        while(cur!=null){
            if(cur.val>key){
                cur = cur.left;
            }else if(cur.val<key){
                cur = cur.right;
            }else{
                return cur;
            }
        }
        return null;
    }
    //删除
    public boolean remove(int key){

    }
}
